from math import sqrt


class Solution:
    """这个方法不对"""
    def numSquares(self, n: int) -> int:
        mid_num = int(sqrt(n))
        if n <= 3:
            return n
        if mid_num ** 2 == n:
            return 1
        return 1 + min(self.numSquares(n - (mid_num - 1) ** 2), self.numSquares(n - mid_num ** 2))


class Solution:
    def numSquares(self, n: int) -> int:
        # while n % 4 == 0:
        #     n /= 4
        # if n % 8 == 7:
        #     return 4
        # a = 0
        # while a ** 2 <= n:
        #     b = int((n - a ** 2) ** 0.5)
        #     if a ** 2 + b ** 2 == n:
        #         return bool(a) + bool(b)
        #     a += 1
        # return 3
        """优化版"""
        while n % 4 == 0:
            n /= 4
        if n % 8 == 7:
            return 4
        a = 0
        while a ** 2 <= n:
            b = (n - a ** 2) ** 0.5
            if b % 1 == 0:
                return bool(a) + bool(b)
            a += 1
        return 3


a = Solution()
print(a.numSquares(4))
print(a.numSquares(12))
print(a.numSquares(13))
print(a.numSquares(28))
print(a.numSquares(10))
